class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        board = [[0 for _ in range(n)] for _ in range(n)]

        def place(r,c,p):
            for i in range(n):
                board[i][c] += p
                board[r][i] += p
            for i in range(-n, n):
                if 0<=r-i<n and 0<=c+i<n:
                    board[r-i][c+i]+=p
                if 0<=r+i<n and 0<=c+i<n:
                    board[r+i][c+i]+=p
            board[r][c] -= p*3

        placement = []

        ret = [0]
        def find(r):
            if r==n:
                ret[0] += 1
                return
            for c in range(n):
                if board[r][c]==0:
                    place(r, c, 1)
                    placement.append(c)
                    find(r+1)
                    placement.pop()
                    place(r, c, -1)
        
        find(0)
        return ret[0]

print(Solution().solveNQueens(8))